package my_bts;

import java.util.NoSuchElementException;

/**
 * 二叉搜索树
 */
public class MyBTS {
    private class Node {
        private int val;
        private Node left;
        private Node right;

        Node(int val) {
            this.val = val;
        }

        Node(int val, Node left, Node right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    private int size;
    private Node root;

    MyBTS() {}
    MyBTS(Node root) {
        this.root = root;
    }

    /**
     * 想二叉搜索树中插入结点，只负责提供值
     * @param val
     */
    public void add(int val) {
        root = add(root, val);
    }

    /**
     * 判断二叉搜索树中是否含有某值的节点
     * @param val
     * @return
     */
    public boolean contains(int val) {
        return contains(root, val);
    }

    /**
     * 寻找二叉搜索树中的最小值
     * @return 返回最小值
     */
    public int findMin() {
        if (size == 0) {
            throw new NoSuchElementException("BST is empty! can't get min!");
        }
        Node node = minNode(root);
        return node.val;
    }

    /**
     * 寻找二叉搜索树中的最大值
     * @return 返回该值
     */
    public int findMax() {
        if (size == 0) {
            throw new NoSuchElementException("BTS is empty! can't get max!");
        }
        Node node = maxNode(root);
        return node.val;
    }

    /**
     * 删除二叉搜索树中的最小值
     * @return
     */
    public int removeMin() {
        if (size == 0) {
            throw new NoSuchElementException("BTS is empty, can't remove!");
        }
        // 可能需要更新root
        int min = findMin();
        root = removeMin(root);
        return min;
    }

    /**
     * 删除二叉搜索树中的最大值
     * @return 返回该最大值
     */
    public int removeMax() {
        if (size == 0) {
            throw new NoSuchElementException("BST is empty, can't remove!");
        }
        int max = findMax();
        root = removeMax(root);
        return max;
    }

    /**
     * 删除指定值的节点
     * @param val
     */
    public void remove(int val) {
        root = remove(root, val);
    }

    /**
     * 删除指定值val的节点
     * @param root
     * @param val
     * @return 返回删除后的根结点
     */
    private Node remove(Node root, int val) {
        if (root == null) {
            throw new NoSuchElementException("There is no node with the value " + val + " in BST!");
        } else if (val < root.val) {
            // 在左子树
            root.left = remove(root.left, val);
            return root;
        } else if (val > root.val) {
            // 在右子树
            root.right = remove(root.right, val);
            return root;
        } else {
            // 当前节点就是待删除节点
            if (root.left == null) {
                Node rightNode = root.right;
                root = null;
                return rightNode;
            }
            if (root.right == null) {
                Node leftNode = root.left;
                root = null;
                return leftNode;
            }
            // 左右子树均不为空，将左子树最大值作为新的根结点
            Node leftMax = maxNode(root.left);
            // 将删除左子树最大值后的根结点作为新根结点的左子树
            leftMax.left = removeMax(root.left); // 注意要先将左最大删除若直接拼接右子树会寻找最大错误
            leftMax.right = root.right;
            root = root.left = root.right = null;
            return leftMax;
        }
    }

    /**
     * 删除二叉搜索树中的最大值节点
     * @param root
     * @return 返回删除后的根结点
     */
    private Node removeMax(Node root) {
        if (root.right == null) {
            Node left = root.left;
            root = root.left = null;
            size --;
            return left;
        }
        root.right = removeMax(root.right);
        return root;
    }

    /**
     * 删除二叉搜索树中的最小值节点
     * @param root
     * @return 返回删除后的根结点
     */
    private Node removeMin(Node root) {
        if (root.left == null) {
            Node right = root.right;
            root = root.right = null;
            size --;
            return right;
        }
        root.left = removeMin(root.left);
        return root;
    }

    /**
     * 寻找二叉搜索树中值最大的节点
     * @param root
     * @return 返回该节点
     */
    private Node maxNode(Node root) {
        if (root.right == null) {
            return root;
        }
        return maxNode(root.right);
    }

    /**
     * 寻找最小节点
     * @return 返回该节点
     * @param root
     */
    private Node minNode(Node root) {
        if (root.left == null) {
            return root;
        }
        return minNode(root.left);
    }

    /**
     * 前序遍历打印二叉搜索树
     * @return
     */
    @Override
    public String toString() {
        StringBuilder str = new StringBuilder();
        generateBSTString(this.root, 0, str);
        return str.toString();
    }


    private Node add(Node root, int val) {
        if (root == null) {
            size ++;
            Node node = new Node(val);
            return node;
        }
        if (val < root.val) {
            root.left = add(root.left, val);
        } else {
            root.right = add(root.right, val);
        }
        return root;
    }

    private boolean contains(Node root, int val) {
        if (root == null) {
            return false;
        }
        if (root.val == val) {
            return true;
        }
        if (val < root.val) {
            return contains(root.left, val);
        }
        return contains(root.right, val);
    }

    private void generateBSTString(Node root, int depth, StringBuilder str) {
        if (root == null) {
            str.append(printGangGang(depth)).append("NULL").append("\n");
            return;
        }
        str.append(printGangGang(depth)).append(root.val).append("\n");
        generateBSTString(root.left, depth + 1, str);
        generateBSTString(root.right, depth + 1, str);
    }

    private String printGangGang(int depth) {
        StringBuilder str = new StringBuilder();
        for (int i = 0; i < depth; i++) {
            str.append("--");
        }
        return str.toString();
    }
}

class Main {
    public static void main(String[] args) {
        MyBTS myBTS = new MyBTS();
        int[] nums = new int[] {4, 1, 3, 5, 2, 0, 7};
        for (int num : nums) {
            myBTS.add(num);
        }
//        System.out.println(myBTS);
//        System.out.println("该二叉搜索树中最小值为" + myBTS.findMin());
//        System.out.println("该二叉搜索树中最大值为" + myBTS.findMax());
//        System.out.println("删除其中最小值" + myBTS.removeMin() + "和最大值" + myBTS.removeMax() +"后的二叉树为：\n" + myBTS);
        int removeNum = 5;
        int nullVoidNum = 10;
        myBTS.remove(removeNum);
        System.out.println("删除值为" + removeNum + "后的二叉搜索树为：\n" + myBTS);
        myBTS.remove(nullVoidNum);
    }
}

